package medium;//给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
//
// 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序
//列。
//
//
// 示例 1：
//
//
//输入：nums = [10,9,2,5,3,7,101,18]
//输出：4
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
//
//
// 示例 2：
//
//
//输入：nums = [0,1,0,3,2,3]
//输出：4
//
//
// 示例 3：
//
//
//输入：nums = [7,7,7,7,7,7,7]
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 2500
// -104 <= nums[i] <= 104
//
//
//
//
// 进阶：
//
//
// 你可以设计时间复杂度为 O(n2) 的解决方案吗？
// 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
//
// Related Topics 数组 二分查找 动态规划
// 👍 1930 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
public class L300 {

    public static void main(String[] args) {
        System.out.println(lengthOfLIS(new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12}));
    }

    public static int lengthOfLIS(int[] nums) {
        //辅助数组+二分
        //辅助数组存储自增
        int[] res = new int[nums.length];
        res[0] = nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            //比最后一个值大
            if (res[cnt - 1] < nums[i]) {
                res[cnt++] = nums[i];
                continue;
            }
            int l = 0;
            int r = cnt - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (res[mid] >= nums[i]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            if (l == cnt) {
                res[l - 1] = nums[i];
            } else
                res[l] = nums[i];
        }
        return cnt;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
